"""
215. 数组中的第K个最大元素
"""
from typing import List


class Solution:

    def findKthLargest(self, nums: List[int], k: int) -> int:
        """
         * 思路：利用快速排序的思路
         * 数组中第k个最大元素，就是对于一个升序的数组（长度为n），取第n - k个元素
         * 遍历数组，查询findSortNum（）方法返回的结果是不是待求结果，是则返回，否则根据值大小调整区间
        @param nums:
        @param k:
        @return:
        """
        k = len(nums) - k
        high = len(nums) - 1
        low = 0

        for i in range(len(nums)):
            sort_num = self.find_sort_nums(nums, low, high)
            if sort_num < k:
                low = sort_num + 1
            elif sort_num > k:
                high = sort_num - 1
            else:
                return nums[sort_num]
        return -1

    def find_sort_nums(self, nums: List[int], low: int, high: int) -> int:
        """
         * 从nums中选择一个元素，使其满足 左边所有元素 < 当前元素 < 右边所有元素
         * 做法：选择第一个元素作为待排序的元素，利用双指针将low放到合适的位置，
         * 1. i指向low + 1，j指向high，
         * 2. 分别让nums[i]和nums[low]比较，nums[j]和nums[low]比较，当nums[low] < nums[i] 且 nums[high] > nums[i]，交换i和j的位置
         *    最后再交换low和j位置的元素
        @param nums: 待排数组
        @param low: 下标
        @param high: 上标
        """
        # 取第一个元素作为待排序元素
        sort_num = nums[low]

        # 利用双指针将low放到合适的位置
        i = low + 1
        j = high
        while i <= j:
            while i < high and nums[i] <= sort_num:
                i += 1
            while j > low and nums[j] > sort_num:
                j -= 1
            if i >= j:
                break
            # 交换i j 的元素
            self.swap(nums, i, j)

        # 交换low和j
        self.swap(nums, low, j)

        return j



    def swap(self, nums: List[int], i: int, j: int):
        """
        交换i j两个元素
        """
        tmp = nums[i]
        nums[i] = nums[j]
        nums[j] = tmp